#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>

enum {
  TK_NOTYPE = 256, 
  TK_EQ = 252,
  TK_NUMBER = 255,
  TK_MUL =48,
  TK_NEG = 254,
  TK_DEREF = 253,
  TK_AND = 251,
  TK_REG = 250,
  /* TODO: Add more token types */

};

static struct rule {
  const char *regex;
  int token_type;
  int priority;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE,0},    // spaces
  {"\\+", '+',3},         // plus
  {"==", TK_EQ,5},        // equal
  {"\\-", '-',3},
  {"[0-9]+",TK_NUMBER,1},
  {"\\*",TK_MUL,4},
  {"\\/",'/',4},
  {"\\(",'(',0},
  {"\\)",')',0},
  {"\\&&",TK_AND,5},
  {"(\\$[0-9]+)|[a-z][a-z]|[a-z][0-9]",TK_REG,1}, 
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
  int priority;
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;
static	int priop;
static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0' && e[position] != 10) {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s,and token.type:%d",
            i, rules[i].regex, position, substr_len, substr_len, substr_start,rules[i].token_type);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        switch (rules[i].token_type) {
	case 256 : /* printf("no type");*/break;
	default:
	tokens[nr_token].type = rules[i].token_type;
//	printf("%d,%d\n",i,rules[i].token_type);
	tokens[nr_token].priority = rules[i].priority;
	if(tokens[nr_token].type == '-' && tokens[nr_token-1].type != TK_NUMBER){ //NEGETIVE 
		tokens[nr_token].type = TK_NEG;
		tokens[nr_token].priority = 2;//higher than number lower than '+' and '-'
	}
	else if (tokens[nr_token].type == TK_MUL  && tokens[nr_token-1].type != TK_NUMBER){ //DEREF
		tokens[nr_token].type = TK_DEREF;
//		printf("point\n");
		tokens[nr_token].priority = 2;//higher than number lower than '+' and '-'
	}

	strncpy(tokens[nr_token].str,substr_start,substr_len);
	nr_token += 1;
        }

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("This char %d no match at position %d\n%s\n%*.s^\n",e[position],position, e, position, "");
      return false;
    }
  }

  return true;
}
bool check_parentheses(int p, int q){
	int i,tag = 0;
	if (tokens[p].type != '(' || tokens[q].type != ')' ){/*`printf("%d,%d,%d\n",tokens[p].type,tokens[q].type,'(');*/return false;}
	for (i = p;i <= q; i++){
		if(tokens[i].type == '(') tag ++;
		else if (tokens[i].type == ')')tag --;
		if (tag == 0 && i <q)
		{	printf("\n");
		return false;}
	}
	if (tag != 0) return false;
//	printf("true para\n");
	return true;
}

int dominant_operator(int p, int q){
	int i, op = p;
	int tag = 0;
	int priority = 0;
	priop = 0;
	for(i = p;i <= q; i++){
//		printf("round:%d,priop = %d,tokentype:%d,priority %d\n",i,priop,tokens[i].type,tokens[i].priority);
		if(tokens[i].type == TK_NUMBER)continue;
		else if(tokens[i].type == '('){
			tag+=1;
			i++;
			while(1){
				if(tokens[i].type == '(') tag +=1;
				else if (tokens[i].type == ')')tag-=1;
				if (tag == 0){
//					printf("break at:%d\n",i);
					break;}
				i++;
			}
			if(i>q)break;
		}
		else if(tokens[i].priority >= priority){
			if(priority == 2 && tokens[i].priority == 2){
				op = op;
			}
			else{
			priority = tokens[i].priority;
			priop = tokens[i].type;
			op = i;}
//			printf("priop %d with priority %d in %d\n",priop,priority,op);
		}
	}
//	printf("%d in %d\n",priop,op);
	return op;
}

word_t eval(int p, int q){
	word_t number = 0;
	int op = 0;
	word_t val1, val2;
	if(p>q){
//	 printf("bad:%d,%d\n",p,q);
	 return 0;
	 }
	 else if (p == q){
	sscanf(tokens[q].str,"%ld",&number);
//	printf("number = %d\n",number);
	return number;
	 }
	 else if(check_parentheses(p,q) == true){
//		printf("check true: %d,%d\n",p+1,q-1);
	 return eval(p+1,q-1);
	 }
	 else{
//		 printf("finding operator between %d and %d\n",p,q);
		 op = dominant_operator(p,q);
		 bool success = false;
		switch (priop){
		case '+': val1 = eval(p,op-1);
			val2 = eval(op+1,q);
			  return val1 + val2;
		case '-': val1 = eval(p,op-1);
		          val2 = eval(op+1,q);
			  return val1 - val2;
		case '/': val1 = eval(p,op-1);
			  val2 = eval(op+1,q);
			  if (val2 == 0)printf("Unvalid Expression in division\n");
			  assert(val2 != 0);
			  return val1 / val2;
		case TK_MUL : val1 = eval(p,op-1);
			      val2 = eval(op+1,q);
			      return val1 * val2;
		case TK_NEG : return -eval(op+1,q);
		case TK_DEREF: 

			     return isa_reg_str2val(tokens[op+1].str,&success);
		case TK_EQ : return (eval(p,op-1)==eval(op+1,q));
		case TK_AND :return (eval(p,op-1) && eval(op+1,q));
		default : val1 = eval(p,op-1);
		 	  val2 = eval(op+1,q);return val1 - val2;	
	       	}
	 }

}

word_t expr(char *e, bool *success) {
word_t result;
    if (!make_token(e)) {
    *success = false;
    return 0;
  }

  /* TODO: Insert codes to evaluate the expression. */

  else{
	int p = 0;
	int q = nr_token-1;
//	printf("%d,%d\n",p,q);
	result = eval(p,q);
//	printf("result: 0x%lx \n",result);	 
    
	*success = true;
	return result;
  }
  return 0;
}


